import java.awt.*;
//Graphics algorithms:
//Bresenham's style:
// WU
// http://www.mini.pw.edu.pl/~kotowski/Grafika/RasterDrawing/Index.html
// Apparently,
// there is a typo:
// ...
// y++;
// if (D(R,y)<T) // Initial T=0, and D >= 0 for circle's points which are not on the grid.
// // Therefore, this condition never works.
// x--;
// ...
class TestsWU {
public static void main( String args[] ) {
Frame[] frmArray = new Frame[8];
//for( int accuracy = 1; accuracy<8; accuracy++ )
for( int iX = 0; iX<5; iX++ )
//accuracy = 8 gives array of 100 000 000 of int32 = 400Mbytes
//which gives java.lang.OutOfMemoryError: Java heap space ...
//in our 1 Gig RAM PC.
{
int accuracy = iX + 3;
frmArray[accuracy] = new Frame();
Frame frm = frmArray[accuracy];
int xSize = 600;
int ySize = 500;
frm.setSize(xSize,ySize);
frm.setVisible(true);
//Toolkit toolkit = frm.getToolkit();
Graphics g = frm.getGraphics();
long start = System.currentTimeMillis();
String s = InitializeISqrt( accuracy );
if( s != "" ){
System.out.println( s );
} else {
System.out.println( "Total Duration=" + ( System.currentTimeMillis() - start) + " milliseconds." );
System.out.println( "Duration per array element =" +
( 1000000. * ( System.currentTimeMillis() - start)) / ISqrt.length +
" nanoseconds." );
int arg = 0;
ISQRT(arg);
prn( "sqrt(" + arg + ")="+ ISignificand + " * 10^-" + IExponent);
arg = 1;
ISQRT(arg);
prn( "sqrt(" + arg + ")="+ ISignificand + " * 10^-" + IExponent);
arg = 20000;
ISQRT(arg);
prn( "sqrt(" + arg + ")="+ ISignificand + " * 10^-" + IExponent);
arg = 999999;
ISQRT(arg);
prn( "sqrt(" + arg + ")="+ ISignificand + " * 10^-" + IExponent);
prn( "Reminder = ID(500,20,255) = " + ID(500,20,255) );
prn("\r\n\r\n\r\n");
int R = 20;
int y=0;
int x=R;
//Center graph according test index, iX:
int xRow = iX/2;
int yColumn = iX % 2;
int xStep = xSize*8/10;
int yStep = ySize*8/10;
int xCenter = xRow * xStep;
int yCenter = yColumn * yStep;
int I = 255;
int squareSize = 10;
int squareSize2 = squareSize/2;
//Make black background to see Intensity well:
g.setColor(new Color(0,0,0));
g.fillRect( 0,0,xSize,ySize);
while( y<x ) {
ISQRT( R*R-y*y );
x = ISignificand;
int p = POWERES_OF_TEN[IExponent];
int id = x % p;
int xLeft = (x - id) / p * squareSize-squareSize2;
int xRight = ((x - id) + p ) / p * squareSize-squareSize2;
//x has been used. Make it real:
x /= p;
int yScaled = y*squareSize+squareSize2;
int ILeft = I*(p-id)/p;
int IRight = I* id /p;
prn("y="+y+" ISignificand="+ISignificand+" p=" + p + " id=" + id + " xLeft="+xLeft+" x=" + x + " xRight="+xRight+ " ILeft="+ILeft+ " IRight="+IRight);
g.setColor(new Color(IRight,IRight,IRight));
g.fillRect( xRight+xCenter, yCenter-yScaled, squareSize, squareSize );
g.setColor(new Color(ILeft,ILeft,ILeft));
g.fillRect( xLeft+xCenter, yCenter-yScaled, squareSize, squareSize );
y +=1;
}//while y<x
y=0;
R = R*squareSize;
x=R;
g.setColor(new Color(255,0,0));
while( y<x ) {
x = (int)Math.sqrt( ((double)R) * R - y * y );
g.drawLine( x+xCenter, yCenter-y,
x+xCenter, yCenter-y );
y+=1;
}
g.setColor(new Color(0,0,255));
g.drawLine( xCenter, yCenter, xCenter+R, yCenter );
g.drawLine( xCenter, yCenter, xCenter, yCenter-R );
} // if( s != "" ){
//Go to next test:
/* try{
char c = (char) System.in.read();
System.out.println( "Char=" + c );
//Not good: System.out.close();
if( c == 'e' ) System.exit(0);
} catch (Exception e) {System.out.println("Exc=" + e);}
frm.dispose();
frm=null;
*/
} //for
/*
System.out.println( "Program Finished.\r\n");
char c = ' ';
while( c != 'e' ) {
try{
c = (char) System.in.read();
System.out.println( c );
} catch (Exception e) {};
}//while
for( int i=1; i<8; i++ ) {
frmArray[i].dispose();
frmArray[i] = null;
}
System.exit(0);
*/
}//main
//To not exceede limts of int32:
private static final int SAFE_DIGITS = 6;
private static int ROOTS_ARRAY_SIZE;
//Redundant digits which exceed accuracy restricted by ACCURACY:
private static int BONUS_DIGITS;
private static int BONUS_MULTIPLIER;
//Auxiliary array to store precalculated powers of 10:
private static int POWERES_OF_TEN[] = { 1, 10, 100, 1000, 10000, 100000, 1000000, 10000000, 100000000, 1000000000 };
//Primary array where precalculated roots will be stored:
private static int[] ISqrt;
//ACCURACY value 3 should provide sqrt(10^3) accuracy ~ 3% accuracy.
//ACCURACY value 4 should provide sqrt(10^4) accuracy ~ 1% accuracy.
// In application to IntegerWU algorithm to find Intensity*ceil(sqrt(RR-yy)),
// this will give 100 grades of shade which should be good.
//ACCURACY value 5 should provide sqrt(10^5) accuracy ~ .3% accuracy.
public static String InitializeISqrt(int ACCURACY) {
System.out.println( "ACCURACY=" + ACCURACY + ". SAFE DIGITS=" + SAFE_DIGITS );
if( ACCURACY < 3 ) {
return "ACCURACY is too small: ACCURACY < " + 3;
}
int w = 2 * SAFE_DIGITS - ACCURACY;
BONUS_DIGITS = (w - (w%2)) / 2;
if( BONUS_DIGITS < 0 ) {
return "ACCURACY is too big: ACCURACY > " + (2 * SAFE_DIGITS);
}
ROOTS_ARRAY_SIZE = POWERES_OF_TEN[ACCURACY];
BONUS_MULTIPLIER = POWERES_OF_TEN[BONUS_DIGITS];
System.out.println( "ROOTS_ARRAY_SIZE=" + ROOTS_ARRAY_SIZE + ". BONUS_DIGITS=" + BONUS_DIGITS + ". BONUS_MULTIPLIER=" + BONUS_MULTIPLIER + ".");
ISqrt = new int[ ROOTS_ARRAY_SIZE ];
for( int i=0; i<ROOTS_ARRAY_SIZE; i++ ){
ISqrt[i] = (int) ( Math.sqrt((double)i) * BONUS_MULTIPLIER );
}
return "";
}
//Calculating square root represented by integer numbers.
//Input x>=0.
//Output: ISignificand * 10^IExponent
// where
public static int IExponent;
public static int ISignificand;
public static void ISQRT( int x ) {
int shift=0;
if ( x!=0 ) {
while ( x<ROOTS_ARRAY_SIZE ) {
x = x*100;
shift -=1;
}
}
while ( x>=ROOTS_ARRAY_SIZE ) {
x = x/100;
shift +=1;
}
IExponent = BONUS_DIGITS-shift;
ISignificand = ISqrt[x];
}
//This function calculates D(R,y).
//It returns distance scaled with FullIntensity.
//Input: FullIntensity < 2000. (To avoid integer overflow when FullIntensity * id.)
private static int ID( int R, int y, int FullIntensity ) {
ISQRT( R*R-y*y );
int p = POWERES_OF_TEN[IExponent];
int id = ISignificand % p;
prn( "ISignificand=" + ISignificand + ". Absolute id=" + id + ". IExponent=" + IExponent + ". p=" + p );
return FullIntensity * id / p;
}
private static void prn( String s ){
System.out.println( s );
}
}
Copyright_C_2008_Landkey_Computers.txt